Search results for "Star height"
showing 2 items of 2 documents
ON THE STAR HEIGHT OF RATIONAL LANGUAGES
1994
Two problems concerning the star height of a rational language are investigated: the star height one problem and the relationships between the unambiguity of an expression and its star height. For this purpose we consider the class of factorial, transitive and rational (FTR) languages. From the algebraic point of view a FTR language is the set of factors of a rational submonoid M. Two subclasses of FTR languages are introduced: renewal languages, corresponding to the case of M finitely generated, and unambiguous renewal languages, corresponding to the case of M finitely generated and free. We prove that a FTR language has star height one if and only if it is renewal. This gives a simple de…
The Star Height One Problem for Irreducible Automata
1993
The star height of a regular expression is, informally, the maximum number of nested stars in the expression. The star height of a regular language is the minimal star height of a regular expression denoting this language. The notion of star height indicates in a certain sense the “loop complexity” of a regular expression and thus it gives a measure of the complexity of a regular language.